package leetcode_300;

/**
 *@author 周杨
 *LongestIncreasingSubsequence_300 找最长连续子序列
 *describe:用动态规划 AC 50%
 *2018年6月29日 下午2:07:01
 */
public class LongestIncreasingSubsequence_300 {

	public static void main(String[] args) {
		LongestIncreasingSubsequence_300 test=new LongestIncreasingSubsequence_300();
		System.out.println(test.lengthOfLIS(new int[] {4,10,4,3,8,9}));

	}
	/**
	 * describe:动态规划 dp保存以本元素为开头的连续最长序列的长度 时间复杂度O(n^2)
	 * 2018年6月29日 下午1:39:15
	 */
	public int lengthOfLIS(int[] nums) {
		if(nums.length==0)
			return 0;
        int dp[]=new int[nums.length];
        dp[nums.length-1]=1;
        int m=1;
        for(int i=nums.length-2;i>=0;--i) {
        	int max=1;
        	for(int j=i+1;j<nums.length;++j) {
        		if(nums[i]<nums[j]) {
        			max=Math.max(max, dp[j]+1);
        		}
        	}
        	dp[i]=max;
        	m=Math.max(m, max);
        }
        return m;
    }
}
